package com.c2b.algorithm.leetcode.base;

import java.util.*;

/**
 * <a href='https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/'>电话号码的字母组合(Letter Combinations of a Phone Number)</a>
 * <p>给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。</p>
 * <p>
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *     <ul>
 *         <li>2: a b c</li>
 *         <li>3: d e f</li>
 *         <li>4: g h i</li>
 *         <li>5: j k l</li>
 *         <li>6: m n o</li>
 *         <li>7: p q r s</li>
 *         <li>8: t u v</li>
 *         <li>9: w x y z</li>
 *     </ul>
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：digits = "23"
 *      输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 *
 * 示例 2：
 *      输入：digits = ""
 *      输出：[]
 *
 * 示例 3：
 *      输入：digits = "2"
 *      输出：["a","b","c"]
 *     </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>0 <= digits.length <= 4</li>
 *         <li>digits[i] 是范围 ["2", "9"] 的一个数字。</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/19 11:44
 */
public class LC0017LetterCombinationsOfPhoneNumber_M {

    static class Solution {
        public List<String> letterCombinations(String digits) {

            Map<Character, String> map = new HashMap<>();
            map.put('2', "abc");
            map.put('3', "def");
            map.put('4', "ghi");
            map.put('5', "jkl");
            map.put('6', "mno");
            map.put('7', "pqrs");
            map.put('8', "tuv");
            map.put('9', "wxyz");
            List<String> retList = new ArrayList<>();
            for (char ch : digits.toCharArray()) {
                if (retList.isEmpty()) {
                    retList.addAll(Arrays.asList(map.get(ch).split("")));
                } else {
                    List<String> tempList = new ArrayList<>();
                    for (String str : retList) {
                        for (Character character : map.get(ch).toCharArray()) {
                            tempList.add(str + character);
                        }
                    }
                    retList = tempList;
                }
            }
            return retList;
        }

        public List<String> letterCombinationsByQueue(String digits) {

            Map<Character, String> dict = new HashMap<>();
            dict.put('2', "abc");
            dict.put('3', "def");
            dict.put('4', "ghi");
            dict.put('5', "jkl");
            dict.put('6', "mno");
            dict.put('7', "pqrs");
            dict.put('8', "tuv");
            dict.put('9', "wxyz");

            Queue<String> queue = new LinkedList<>();
            for (char ch : digits.toCharArray()) {
                char[] chars = dict.get(ch).toCharArray();
                if (queue.isEmpty()) {
                    for (char letter : chars) {
                        queue.offer(String.valueOf(letter));
                    }
                } else {
                    int size = queue.size();
                    for (int i = 0; i < size; i++) {
                        String preStr = queue.poll();
                        for (char aChar : chars) {
                            queue.offer(preStr + aChar);
                        }
                    }
                }
            }
            return new LinkedList<>(queue);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        for (String string : solution.letterCombinationsByQueue("23")) {
            System.out.print(string + "  ");
        }
        System.out.println();

        for (String string : solution.letterCombinationsByQueue("")) {
            System.out.print(string + "  ");
        }
        System.out.println();

        for (String string : solution.letterCombinationsByQueue("2")) {
            System.out.print(string + "  ");
        }
        System.out.println();
    }
}
